package com.leetcode.offer;

import java.util.Arrays;

/**
 * @author zfl
 * @Classname MajorityElement
 * @Description 数组中出现次数超过一半的数字
 * @Date 2020/11/10 15:08
 */
public class MajorityElement {

    /**
     * @param nums
     * @return
     * 执行用时：2 ms, 在所有 Java 提交中击败了68.93%的用户
     * 内存消耗：41.8 MB, 在所有 Java 提交中击败了78.77%的用户
     */
    public static int majorityElement1(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }

    /**
     * @param nums
     * @return
     * 执行用时：1 ms, 在所有 Java 提交中击败了99.95%的用户
     * 内存消耗：41.5 MB, 在所有 Java 提交中击败了95.48%的用户
     */
    public static int majorityElement2(int[] nums) {
        int x = 0, votes = 0;
        for (int num : nums) {
            if(votes == 0) {
                x = num;
            }
            votes += num == x ? 1 : -1;
        }
        return x;
    }
}
